1. Field of the Invention
This invention relates to modular multipliers, and more particularly, to a systolic linear-array modular multiplier with pipeline processing elements (PE) which can effectively perform a modular multiplier algorithm which is a modified version of the algorithm of P. L. Montgomery.
2. Description of Related Art
In this information age, the advent of high-speed computers and global communication networks allow people anywhere around the world to process and exchange information conveniently. Various network systems, such as the INTERNET system, allow the people to gain access to information bases that are located at remote places all around the world. In the use of these network system, it is important to keep data from illegal access. The public-key cryptosystem, for example, is a widely used scheme to protect network systems from being accessed by unauthorized users.
Large-operand modular multiplication is the core computation of many public-key cryptosystems, such as the RSA (Rivest-Shamir-Adleman) system which is a public-key cryptosystem proposed by R. L. Riverst, A. Shamir, and L. Adleman. It includes a series of modular multiplication steps, which involve large operands as large as 512 bits in length. The modular multiplication is thus quite complex and time-consuming to perform by conventional computers. To solve the speed problem, a widely used scheme is to arrange a number of processing elements (PE) in a so-called systolic array that allows the modular multiplication steps to be carried out in parallel, thereby significantly increasing the encryption/decryption speed of public keys. This scheme is also suitable for VLSI (very large-scale integration) implementation. Many research papers have proposed various kinds of architectures for implementing a modular multiplier in systolic array. To name a few, C. K. Koc et al. have published a paper entitled "Bit-level Systolic Arrays for Modular Multiplication" in J. VLSI Signal Processing, Vol. 3, pp. 215-223, 1991; C. D. Walter has published a paper entitled "Systolic Modular Multiplication" in IEEE Trans. Comput., Vol. 42, No. 3, pp.376-8; P. Kornerup has published a paper entitled "A Systolic Linear-array Multiplier For A Class Of Right-Shift Algorithms" in IEEE Trans. Comput., Vol. 43, No. 8, pp. 892-898, August 1994; and Weixin Gai et al (who are also the inventors of this application) have published a paper entitled "A Systolic Linear Array For Modular Multiplication" in the 2nd International Conference on ASIC Proceedings (ASICON'96), Shanghai, pp. 171-174, October 1996.
The modular multipliers suggested by these papers, however, are still unsatisfactory in performance, in that the modular multiplier proposed by C. K. Koc et al. uses a clock signal of a very low rate that causes the processing time required to produce the output to be in the order of 13n/2, where n is the number of bits of the operands involved in the modular multiplication; the modular multiplier proposed by C. D. Walter requires a total of about four trillion (4.times.10.sup.12) gates to implement, which makes the manufacturing cost very high; the modular multiplier proposed by P. Kornerup uses a clock signal of about 100 THz (tera-hertz) that allows for an encryption speed in the order of 10.sup.5 bits per second, which is still considered unsatisfactory; and the modular multiplier proposed by Weixin Gai et al uses a clock signal of about 200 THz, but the encryption thereof is similar in performance to that of the modular multiplier proposed by P. Komerup, which is still considered unsatisfactory.
There exists, therefore, a need for a new modular multiplier which can provide an increased performance for the modular multiplication required in public-key cryptosystems, and also a reduced degree of complexity in architecture so as to reduce the manufacturing cost thereof.